package 非线性结构.树;

import 非线性结构.树.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class BinarySearchTree<E> implements ITree<E>, BinaryTreeInfo {


    public static class Node<E> {
        public E element;
        public Node<E> parent;
        public Node<E> left;
        public Node<E> right;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }


        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }


    }

    private Node<E> root;//根节点
    private int size;
    private Comparator<E> comparator;

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    @Override
    public void add(E element) {
        if (root == null) {
            root = new Node<E>(element, null);
            size++;
        } else {
            //1.找到元素摆放父节点
            Node<E> temp = root;
            Node<E> parent = root;
            int tag = -1;
            while (temp != null) {
                int result = compare(element, temp.element);
                tag = result;
                parent = temp;
                if (result > 0) {
                    temp = temp.right;
                } else if (result < 0) {
                    temp = temp.left;
                } else {
                    return;
                }
            }
            //2.把元素添加到父节点对应位置
            Node<E> newNode = new Node<>(element, parent);
            if (tag > 0) {
                parent.right = newNode;
            } else {
                parent.left = newNode;
            }
            size++;
        }
    }

    @Override
    public E remove(E element) {
        return remove(node(element));
    }

    @Override
    public void clear() {
        root = null;
        size = 0;
    }

    private E remove(Node<E> node) {
        if (node == null) return null;

        size--;

        if (node.hasTwoChildren()) { // 度为2的节点
            // 找到后继节点
            Node<E> s = successor(node);
            // 用后继节点的值覆盖度为2的节点的值
            node.element = s.element;
            // 删除后继节点
            node = s;
        }

        // 删除node节点（node的度必然是1或者0）
        Node<E> replacement = node.left != null ? node.left : node.right;

        if (replacement != null) { // node是度为1的节点
            // 更改parent
            replacement.parent = node.parent;
            // 更改parent的left、right的指向
            if (node.parent == null) { // node是度为1的节点并且是根节点
                root = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else { // node == node.parent.right
                node.parent.right = replacement;
            }
        } else if (node.parent == null) { // node是叶子节点并且是根节点
            root = null;
        } else { // node是叶子节点，但不是根节点
            if (node == node.parent.left) {
                node.parent.left = null;
            } else { // node == node.parent.right
                node.parent.right = null;
            }
        }
        return node.element;
    }

    private Node<E> node(E element) {
        Node<E> temp = this.root;
        while (temp == null) {
            int rel = compare(element, temp.element);
            if (rel == 0) return temp;
            if (rel > 0) {
                temp = temp.right;
            } else {
                temp = temp.left;
            }
        }
        return temp;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object element) {
        return false;
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>) node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
//        return myNode.element + "_p(" + parentString + ")";
        return myNode.element;
    }

    /**
     * 前序遍历 根左右
     */
    public void preOrderTraversal(Visitor<E> visitor) {
        preOrderTraversal(root, visitor);
    }

    private void preOrderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        preOrderTraversal(node.left, visitor);
        preOrderTraversal(node.right, visitor);
    }

    /**
     * 中序遍历 左根右
     */
    public void inOrderTraversal(Visitor<E> visitor) {
        inOrderTraversal(root, visitor);
    }

    private void inOrderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        inOrderTraversal(node.left, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inOrderTraversal(node.right, visitor);
    }

    /**
     * 后序遍历 左右根
     */
    public void postorderTraversal(Visitor<E> visitor) {
        postorderTraversal(root, visitor);
    }

    private void postorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        postorderTraversal(node.left, visitor);
        postorderTraversal(node.right, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }

    /**
     * 层序遍历
     */
    public void levelOrderTraversal(Visitor<E> visitor) {
        levelOrderTraversal(root, visitor);
    }

    private void levelOrderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null) return;

        Queue<Node<E>> queue = new LinkedBlockingQueue<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            //1.取出根节点
            Node<E> cur = queue.poll();
            boolean visit = visitor.visit(cur.element);
            if (visit) return;
            //2.放入左右节点
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    private int compare(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>) e1).compareTo(e2);
    }

    //返回树的高度
    public int height() {
        return heightByPreOrder(root);
    }

    private int heightByLevelOrder(Node<E> node) {
        if (node == null) return 0;

        int height = 0;
        int size = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            Node<E> curNode = queue.poll();
            size--;
            if (curNode.left != null) {
                queue.offer(curNode.left);
            }

            if (curNode.right != null) {
                queue.offer(curNode.right);
            }

            if (size == 0) {
                size = queue.size();
                height++;
            }
        }

        return height;
    }

    /**
     * ┌──7──┐
     * │     │
     * ┌─4─┐ ┌─9─┐
     * │   │ │   │
     * ┌─2─┐ 5 8   11─┐
     * │   │          │
     * 1   3          12
     */
    private int heightByPreOrder(Node<E> node) {
        if (node == null) return 0;
        int a = heightByPreOrder(node.left);
        int b = heightByPreOrder(node.right);
        return 1 + Math.max(a, b);
    }

    //是否是完全二叉树（所有叶子节点靠左显示）
    public boolean isComplete() {
        if (root == null) return false;

        Queue<Node<E>> nodeQueue = new LinkedList<>();
        nodeQueue.offer(root);

        boolean leaf = false;//标记是否剩下都是叶子节点
        while (!nodeQueue.isEmpty()) {
            Node<E> curNode = nodeQueue.poll();
            if (leaf && !curNode.isLeaf()) return false;

            if (curNode.left != null) {
                nodeQueue.offer(curNode.left);
            } else if (curNode.right != null) {
                return false;
            }

            if (curNode.right != null) {
                nodeQueue.offer(curNode.right);
            } else {
                leaf = true;
            }
        }
        return true;
    }

    //前驱节点 中序遍历时的前一个节点
    public Node<E> predecessor(Node<E> node) {
        if (node == null) return null;
        Node<E> left = node.left;
        if (left != null) {//1.如果左节点不等于空
            while (left.right != null) {
                left = left.right;
            }
            return left;
        } else if (node.parent != null) { //2.左节点为空 ，父节点不为空
            while (node != node.parent.right) {
                node = node.parent;
            }
            return node.parent;
        } else { //2.左节点为空 ，父节点为空
        }
        return null;
    }

    //后驱节点 中序遍历时的后一个节点
    public Node<E> successor(Node<E> node) {
        if (node == null) return null;
        Node<E> right = node.right;
        if (right != null) {//1.如果右节点不等于空
            while (right.left != null) {
                right = right.left;
            }
            return right;
        } else if (node.parent != null) { //2.右节点为空 ，父节点不为空
            while (node != node.parent.left) {
                node = node.parent;
            }
            return node.parent;
        } else { //2.右节点为空 ，父节点为空
        }
        return null;
    }

    public static abstract class Visitor<E> {
        boolean stop;

        /**
         * @param element
         * @return 返回true 代表停止遍历
         */
        public abstract boolean visit(E element);
    }
}
